package com.company;

import java.util.List;



public class Main {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        } else if(list2 == null) {
            return list1;
        } else if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }

    public static void main(String[] args) {
	// write your code here
        //创建链表1
        ListNode list1Sta = new ListNode(1);
        ListNode list1Next;
        list1Next = list1Sta;

        for(int i = 2; i <= 4; i++) {
            if (i != 3) {
                ListNode node = new ListNode(i);
                list1Next.next = node;
                list1Next = list1Next.next;
            }
        }
        list1Next = list1Sta;
        System.out.println("list1中的节点:");
        print(list1Next);

        //创建链表2
        ListNode list2Sta = new ListNode(1);
        ListNode list2Next;
        list2Next = list2Sta;

        for(int i = 3; i <= 4; i++) {

            ListNode node = new ListNode(i);
            list2Next.next = node;
            list2Next = list2Next.next;
        }
        list2Next = list2Sta;
        System.out.println("list2中的节点:");
        print(list2Next);

        System.out.println("合并这两个升序链表后得到的新链表的节点:");
        print(mergeTwoLists(list1Next,list2Next));

    }

    public static void print(ListNode n){
        //创建链表节点
        while(n != null){
            System.out.println("节点:" + n.val);
            n = n.next;
        }
        System.out.println();
    }
}



